package com.uow.algdemo.algorithms;

import java.util.ArrayList;
import java.util.List;

import android.util.Log;

/**
 * This class will receive data of two string and search the string use string matching algorithms, then generate animation steps.
 */
public class StringMatching
{
	/**
     * This is the pattern of string.
     */
	private String pattern;
	/**
     * This is the text for search.
     */
	private String text;
    /**
     * This array contains skip table for string matching algorithms.
     */
	private int[] skipTable;
	/**
     * This is the hash value for pattern.
     */
	private int hash;
	/**
     * This array contains steps of string matching animation.
     */
	private List<int[][]> steps = new ArrayList<int[][]>();
	/**
	 * @param newText The string of original.
     * @param newPattern Text for search.
	 */
	public StringMatching(String newText, String newPattern)
	{
		text = newText;
		pattern = newPattern;
	}
	/**
	 * @return The skipTable
	 */
	public int[] getSkipTable()
	{
		return skipTable;
	}
	/**
	 * @return The steps
	 */
	public List<int[][]> getSteps()
	{
		return steps;
	}

	/**
     * This method records steps for compare two chars.
     * @param tPos Position of target string.
     * @param mPos Position of keyword string.
     */
	private void compare(int tPos, int mPos)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 0;
		tmp[1][0] = tPos;
		tmp[2][0] = mPos;
		steps.add(tmp);
	}
	
    /**
     * This method records step of moving texts.
     * @param step Step for moving text.
     */
	private void skip(int step)
	{
		int[][] tmp = new int[2][1];
		tmp[0][0] = 1;
		tmp[1][0] = step;
		steps.add(tmp);
	}
	/**
     * This method generate step of clear status of animation.
     */
	private void clear()
	{
		int[][] tmp = new int[1][1];
		tmp[0][0] = 2;
		steps.add(tmp);
	}
	/**
     * This method will search text from original string use algorithm of Morris Pratt, then records steps to list of steps.
     */
	public void stringMatchingMorrisPratt()
	{
		int n = text.length();
		int m = pattern.length();

		int length = pattern.length();
		skipTable = new int[length+1];
		
		skipTable[0] = 0;
		
		int k = 0;
		for(int i = 1; i < length; i++)
		{
			while(k > 0 && pattern.charAt(k) != pattern.charAt(i))
				k = skipTable[k -1];

			if(pattern.charAt(k) == pattern.charAt(i))
				k++;

			skipTable[i] = k;
		}
		for(int i=length; i>0; i--)
		{
			skipTable[i]=skipTable[i-1];
		}
		skipTable[0]=-1;

		int q = 0;
		
		for(int i = 0; i < n; i++)
		{
			while(q >= 0 && pattern.charAt(q) != text.charAt(i))
			{
				compare(i, q);
				clear();
				if(q != 0)
				{
					skip(q - skipTable[q]);
					q = skipTable[q];
				}
				else
				{
					skip(1);
					break;
				}
			}

			if(pattern.charAt(q) == text.charAt(i))
			{
				compare(i, q);
				q++;
			}

			if(q == m)
			{
				clear();
				skip(q - skipTable[q]);
				q = skipTable[q];
			}
		}
	}
	/**
     * This method will search text from original string use algorithm of Knuth Morris Pratt, then records steps to list of steps.
     */
	public void stringMatchingKnuthMorrisPratt()
	{
		int n = text.length();
		int m = pattern.length();

		int length = pattern.length();
		skipTable = new int[length + 1];
		
		skipTable[0] = 0;
		
		int k = 0;
		for(int i = 1; i < length; i++)
		{
			while(k > 0 && pattern.charAt(k) != pattern.charAt(i))
				k = skipTable[k -1];

			if(pattern.charAt(k) == pattern.charAt(i))
				k++;

			skipTable[i] = k;
		}
		for(int i=length; i>0; i--)
		{
			skipTable[i]=skipTable[i-1];
		}
		skipTable[0]=-1;
		
		for(int i = 1; i < length; i++)
		{
			for(int j = 0; j < i; j++)
			{
				if(pattern.charAt(i) == pattern.charAt(j))
				{
					skipTable[i] = skipTable[j];
					break;
				}
			}
		}

		int q = 0;
		
		for(int i = 0; i < n; i++)
		{
			
			while(q >= 0 && pattern.charAt(q) != text.charAt(i))
			{
				compare(i, q);
				clear();
				
				if(q != 0)
				{
					skip(q - skipTable[q]);
					q = skipTable[q];
					
				}
				else
				{
					skip(1);
					break;
				}
			}
			if(q==-1)
			{
				q=0;
			}

			if(pattern.charAt(q) == text.charAt(i))
			{
				compare(i, q);
				q++;
			}

			if(q == m)
			{
				clear();
				skip(q - skipTable[q]);
				q = skipTable[q];
				
			}
			
		}
	}
	/**
     * This method will search text from original string use algorithm of Boyer Moore, then records steps to list of steps.
     */
	public void stringMatchingBoyerMoore()
	{
        // position of rightmost occurrence of c in the pattern
        skipTable = new int[256];
        for (int c = 0; c < 256; c++)
        	skipTable[c] = -1;
        for (int j = 0; j < pattern.length(); j++)
        	skipTable[pattern.charAt(j)] = j;
        
        int M = pattern.length();
        int N = text.length();
        int next;
        for (int i = 0; i <= N - M; i += next)
        {
        	next = 0;
            for (int j = M-1; j >= 0; j--)
            {
            	compare(i+j,j);
                if (pattern.charAt(j) != text.charAt(i+j))
                {
                	next = Math.max(1, j - skipTable[text.charAt(i+j)]);
                    clear();
                    skip(next);
                    break;
                }
            }
            if (next == 0)
			{
				Log.v("BM", "Pattern occurs at  " + i);
				next = Math.max(1, (M-1)- skipTable[text.charAt(i+(M-1))]);
				clear();
                skip(next);
			}
        }
	}
	/**
     * This method will search text from original string use algorithm of Karp Rabin, then records steps to list of steps.
     */
	public void stringMatchingKarpRabin()
	{
		hash = RKHash(pattern);
		skipTable = new int[1];
		skipTable[0] = hash;
		
		int n = text.length();
		int m = pattern.length();
		
		for(int i = 0; i < n; i++)
		{
			if(i + m <= n)
			{
				if(hash == RKHash(text.substring(i, i + m)))
				{
					int j = 0;
					for(j = 0; j < m; j++)
					{
						compare(i+j,j);
						if(text.charAt(i+j) != pattern.charAt(j))
						{
							break;
						}
					}
					if(j == m)
					{
						Log.v("KR", "Pattern occurs at  " + i);
					}
				}
			}
			clear();
			skip(1);
		}
	}
	/**
     * This method hash a string.
     * @param txt String for hash.
     */
	private int RKHash(String txt)
	{
		int m = txt.length();
        int hp = 0;
		int	d = 26, q = 13;

		for(int i = 0 ; i < m; i++)
		{
			hp = (d * hp + txt.charAt(i)) % q;
		}
		
		return hp;
	}
}
